package stack;

import java.util.Deque;
import java.util.LinkedList;
/**
 * @author dx
 * @version 1.0
 * @date 2022/3/28 10:47
 * @description: 仅使用两个栈实现先入先出队列，队列应当支持一般队列支持的所有操作(push、pop、peek、empty)
 *
 * 思路：队列是一种先进先出的数据结构，队列中的元素都从后端(real)入队(push)，从前端(front)出队(pop)
 * 为了满足队列的FIFO的特性，需要用到两个栈，用其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。
 * 每次入队  先把栈1（按队列存储的） 倒腾到 栈2（栈顶就是队列的最后一个元素）  然后把新元素放到栈2    重新再放到栈1中  新元素就放在了栈1的最后
 */
public class Stack_to_Queue {

    Deque<Integer> stack1 = null;
    Deque<Integer> stack2 = null;
    private int front;

    public Stack_to_Queue(){
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }

    public void push(int x){
        if(stack1.isEmpty())
            front = x;
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        stack2.push(x);
        while (!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
    }
    public int pop(){
        return stack1.pop();
    }
    public int peek(){
        return stack1.peek();
    }
    public boolean empty(){
        return stack1.isEmpty();
    }
}